The video also shows rolling dice (briefly), if one wishes to stretch its relevance to include Monte Carlo as well.
Thursday, October 26, 2006
Schrodinger equation in the mass media
The Schrodinger equation appears in the background in the second half of Weird Al's video White & Nerdy.
Friday, October 20, 2006
The Other QMC
Quasi-Monte Carlo is the other method commonly referred to by the QMC acronym (I will abbreviate it QuasiMC to minimize confusion). It's not really Monte Carlo since the sequence of points is not random, but the point sets do have a Monte Carlo-ish feel about them.
And in fact, it does share the property of arbitrary termination with Monte Carlo integration (consider a grid - you have have use all the points at a particular spacing. Stopping half way across the region of integration is not going to yield good results).
The reason people are interested in QuasiMC is that its convergence is better than the 1/sqrt(N) of Monte Carlo. It does this by using point sets that are more evenly distributed than random points - there are fewer clumps of points or large gaps that appear in random sequences (Search for 'Low-discrepancy sequences'. Here's the Wikipedia entries for a technical discussion and some sequences).
QuasiMC point sets are usually generated from sequences where the low-discrepancy condition can be verified theoretically, but it is possible to use the intuitive approach of making the points maximally spread out (see this presentation for an example).
The following algorithm will generate a set of N points that gives better convergence than random (at least it worked on a simple integrand in one dimension.)
(I'm not saying this an efficient way to generate the points, just that it can be done.)
For addition information, see also chapter 7.7 in Numerical Recipes
And in fact, it does share the property of arbitrary termination with Monte Carlo integration (consider a grid - you have have use all the points at a particular spacing. Stopping half way across the region of integration is not going to yield good results).
The reason people are interested in QuasiMC is that its convergence is better than the 1/sqrt(N) of Monte Carlo. It does this by using point sets that are more evenly distributed than random points - there are fewer clumps of points or large gaps that appear in random sequences (Search for 'Low-discrepancy sequences'. Here's the Wikipedia entries for a technical discussion and some sequences).
QuasiMC point sets are usually generated from sequences where the low-discrepancy condition can be verified theoretically, but it is possible to use the intuitive approach of making the points maximally spread out (see this presentation for an example).
The following algorithm will generate a set of N points that gives better convergence than random (at least it worked on a simple integrand in one dimension.)
- compute some random points (>> N points)
- pick a starting point and put it in the set S.
- find the point that is the furthest from all existing points in S, and place that point in S.
- repeat the step 3 until N points are selected.
(I'm not saying this an efficient way to generate the points, just that it can be done.)
For addition information, see also chapter 7.7 in Numerical Recipes
Subscribe to:
Posts (Atom)